#include "QuadTree.h"

QuadTree::QuadTree(int w,int h)
{
	_mapWidth=w;
	_mapHeight=h;
	_pRoot=new QuadNode(0,0,_mapWidth,_mapHeight);
	_count=0;
}
void QuadTree::Add(QuadNode *root,Object *Ob)
{	
	if(root!=NULL)
	{
		//0: Add ....1: Left_Top..... 2: Right_Top....... 3: Left_Bottom...... 4: Right_Bottom
		int result=0;//add here

		int objWidth	=	Ob->_pRECT->right - Ob->_pRECT->left;
		int objHeight	=	Ob->_pRECT->bottom - Ob->_pRECT->top;

		int rectWidth	=	root->_rect->right - root->_rect->left; 
		int rectHeight	=	root->_rect->bottom - root->_rect->top;

		int rectWidthNew=	(root->_rect->right + root->_rect->left)/2; //divide RECT root to quad RECT
		int rectHeightNew=	(root->_rect->bottom + root->_rect->top)/2;

		if((objWidth*objHeight > rectWidth*rectHeight/4) || //check obj have into root RECT
			(rectWidthNew > Ob->_pRECT->left && rectWidthNew <= Ob->_pRECT->right)||
			(rectHeightNew > Ob->_pRECT->top && rectHeightNew <= Ob->_pRECT->bottom))
			result=0;//Add here
		else
		{
			if(Ob->_pRECT->left >= root->_rect->left &&
				Ob->_pRECT->left < rectWidthNew &&
				Ob->_pRECT->top >= root->_rect->top &&
				Ob->_pRECT->top < rectHeightNew)//Left_Top
				result =1;
			else 
				if(Ob->_pRECT->left < root->_rect->right &&
					Ob->_pRECT->left >= rectWidthNew &&
					Ob->_pRECT->top >= root->_rect->top &&
					Ob->_pRECT->top < rectHeightNew)//Right_Top
					result =2;
				else 
					if(Ob->_pRECT->left >= root->_rect->left &&
						Ob->_pRECT->left < rectWidthNew &&
						Ob->_pRECT->top >= rectHeightNew &&
						Ob->_pRECT->top < root->_rect->bottom)//Left_Bottom
						result=3;
					else//Right_Bottom
						result=4;
		}

		if(result==0)//Add here
		{
			root->listObj.push_back(Ob);
			_count++; 
		}
		else
		{
			if(rectWidth/2 > LIM_W_H && rectHeight/2 > LIM_W_H)
			{
				switch(result)
				{
				case 1://Left_Top
					if(root->LT==NULL)
						root->LT=new QuadNode(root->_rect->left,root->_rect->top,rectWidth/2,rectHeight/2);
					Add(root->LT,Ob);
					break;
				case 2://Right_Top
					if(root->RT==NULL)
						root->RT=new QuadNode(rectWidthNew,root->_rect->top,rectWidth/2,rectHeight/2);
					Add(root->RT,Ob);
					break;
				case 3://Left_Bottom
					if(root->LB==NULL)
						root->LB=new QuadNode(root->_rect->left,rectHeightNew,rectWidth/2,rectHeight/2);
					Add(root->LB,Ob);
					break;
				case 4://Right_Bottom
					if(root->RB==NULL)
						root->RB=new QuadNode(rectWidthNew,rectHeightNew,rectWidth/2,rectHeight/2);
					Add(root->RB,Ob);
					break;
				}
			}
		}
	}
}

bool QuadTree::CheckPointInRECT(int x,int y,RECT rect)
{
	if(x >= rect.left && x <= rect.right && y >= rect.top && y <= rect.bottom)
		return true;
	return false;
}
bool QuadTree::CheckRECTInRECT(RECT r,RECT rect)
{
	if(CheckPointInRECT(r.left,r.top,rect)
		||CheckPointInRECT(r.right,r.top,rect)
		||CheckPointInRECT(r.left,r.bottom,rect)
		||CheckPointInRECT(r.right,r.bottom,rect)
		||(rect.top<=r.top&&rect.bottom>=r.bottom&&r.left<=rect.left&&r.right>=rect.right))
	{
		return true;
	}
	return false;
}
void QuadTree::GetObjInRec(QuadNode* root,RECT Screen,vector<Object*> &result)
{
	for(int i=0;i<root->listObj.size();i++)
		if(CheckRECTInRECT(*root->listObj[i]->_pRECT,Screen)||CheckRECTInRECT(Screen,*root->listObj[i]->_pRECT))//active items on camera
		{
			if(!root->listObj[i]->_isActive)//Active enemies
			{
				root->listObj[i]->_isActive=true;
			}
			result.push_back(root->listObj[i]);
		}
		if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,Screen)||CheckRECTInRECT(Screen,*root->LT->_rect)))
			GetObjInRec(root->LT,Screen,result);
		if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,Screen)||CheckRECTInRECT(Screen,*root->RT->_rect)))
			GetObjInRec(root->RT,Screen,result);
		if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,Screen)||CheckRECTInRECT(Screen,*root->LB->_rect)))
			GetObjInRec(root->LB,Screen,result);
		if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,Screen)||CheckRECTInRECT(Screen,*root->RB->_rect)))
			GetObjInRec(root->RB,Screen,result);
}
void QuadTree::DrawObjects(int VirtualLeft,RECT Screen)
{
	vector<Object*> result;
	GetObjInRec(_pRoot,Screen,result);
	for(int j=0;j<=2;j++)//ve tung layer
		for(int i=0;i<result.size();i++)
			if(result[i]->_layer==j)
				result[i]->Draw(VirtualLeft,0);
}
Object* QuadTree::CheckCollision(QuadNode *root,RECT r,int Seq)
{	
	for(int i=0;i<root->listObj.size();i++)
		if(root->listObj[i]->_typeObj!=-1//Day la nhung Object chi dung de trang tri
			&&root->listObj[i]->_status!=2//Chua chet
			&&root->listObj[i]->_id!=Seq
			&&(CheckRECTInRECT(*root->listObj[i]->_pRECT,r)||CheckRECTInRECT(r,*root->listObj[i]->_pRECT)))
			return root->listObj[i];//Dung do
	if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
	{
		Object *ob=CheckCollision(root->LT,r,Seq);
		if(ob!=NULL)
			return ob;
	}
	if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
	{
		Object *ob=CheckCollision(root->RT,r,Seq);
		if(ob!=NULL)
			return ob;
	}
	if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
	{
		Object *ob=CheckCollision(root->LB,r,Seq);
		if(ob!=NULL)
			return ob;
	}
	if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
	{
		Object *ob=CheckCollision(root->RB,r,Seq);
		if(ob!=NULL)
			return ob;
	}
	return NULL;
}

void QuadTree::CheckCollision(QuadNode *root,RECT r,int Seq,vector<Object*>&result)
{	
	for(int i=0;i<root->listObj.size();i++)
		if(root->listObj[i]->_typeObj!=-1//Day la nhung Object chi dung de trang tri
			&&root->listObj[i]->_status!=2//Chua chet
			&&root->listObj[i]->_id!=Seq
			&&(CheckRECTInRECT(*root->listObj[i]->_pRECT,r)||CheckRECTInRECT(r,*root->listObj[i]->_pRECT)))
		{
			//Object* obj= root->listObj[i];
			result.push_back(root->listObj[i]);
		}
	if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
	{
		CheckCollision(root->LT,r,Seq,result);
	
	}
	if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
	{
		CheckCollision(root->RT,r,Seq,result);
	
	}
	if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
	{
		CheckCollision(root->LB,r,Seq,result);
	
	}
	if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
	{
		CheckCollision(root->RB,r,Seq,result);
	}

}
bool QuadTree::IsOnObject(RECT *rect,int Seq)//duoi chan object la object khac hay la khoang trong
{
	RECT r;
	r.left=rect->left;r.right=rect->right;
	r.top=rect->top+1;r.bottom=rect->bottom+1;
	vector<Object*> result;
	CheckCollision(_pRoot,r,Seq,result);
	for(int i=0;i<result.size();i++)
	{
		Object* obj=result[i];
		if(obj->_typeObj==0)
			return true;
	}
	
	return false;
}
void QuadTree::UpdatePosition(QuadNode *root)
{
	for(unsigned int i=0;i<root->listObj.size();i++)
	{
		Object *Ob=root->listObj[i];
		if(Ob->_typeObj!=-1&&Ob->_typeObj!=1&&Ob->_isActive)
		{
			if(Ob->_pRECT->top>WINDOW_HEIGHT
				||(Ob->_pSprite->_totalExistTime!=0&&Ob->_status==2&&GetTickCount()-Ob->_pSprite->_rootTime >=(DWORD)Ob->_pSprite->_totalExistTime))
			{
				Ob->Release();
				root->listObj.erase(root->listObj.begin()+i);
				i--;
				break;
			}
			int a=Ob->Move();
			if(a!=0)
			{
				root->listObj.erase(root->listObj.begin()+i);
				i--;
				this->Add(_pRoot,Ob);
			}
		}
	}
	if(root->LT!=NULL)
		UpdatePosition(root->LT);
	if(root->RT!=NULL)
		UpdatePosition(root->RT);
	if(root->LB!=NULL)
		UpdatePosition(root->LB);
	if(root->RB!=NULL)
		UpdatePosition(root->RB);
}

QuadTree::~QuadTree(void)
{
}

void QuadTree::GetAllObj(QuadNode *root,vector<Object*> &result)
{
	
	for(int i=0;i<root->listObj.size();i++)
		result.push_back(root->listObj[i]);

	if(root->LT!=NULL)
		GetAllObj(root->LT,result);

	if(root->LB!=NULL)
		GetAllObj(root->LB,result);

	if(root->RT!=NULL)
		GetAllObj(root->RT,result);

	if(root->RB!=NULL)
		GetAllObj(root->RB,result);
}

void QuadTree::RemoveAll(QuadNode *root)
{
	if (root!=NULL)
	{
		root->listObj.clear();
	}
	if (root->LB!=NULL)
		RemoveAll(root->LB);
	if (root->LT!=NULL)
		RemoveAll(root->LB);
	if (root->RB!=NULL)
		RemoveAll(root->LB);
	if (root->RT!=NULL)
		RemoveAll(root->LB);
}